package com.zlk.algorithm.algorithm.dynamicPlan.threeDimension;

import java.net.HttpRetryException;

// 矩阵中和能被 K 整除的路径
// 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
// 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
// 请你返回路径和能被 k 整除的路径数目
// 由于答案可能很大，返回答案对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
public class Code04_PathsDivisibleByK {


    public static void main(String[] args) {
        Code04_PathsDivisibleByK test = new Code04_PathsDivisibleByK();
        int[][] grid = new int[][]{
                {5,2,4},{3,0,5},{0,7,2}
        };
        int k=3;
        System.out.println(test.numberOfPaths(grid, k));
    }


    public int numberOfPaths(int[][] grid, int k) {
        int n = grid.length;
        int m = grid[0].length;
        int[][][] dp = new int[k][n][m];
        dp[grid[n-1][m-1]%k][n-1][m-1] = 1;

        for (int i = n - 2; i >= 0; i--) {
            for (int r = 0; r < k; r++) {
                dp[r][i][m - 1] = dp[(k + r - grid[i][m - 1] % k) % k][i + 1][m - 1];
            }
        }
        for (int j = m - 2; j >= 0; j--) {
            for (int r = 0; r < k; r++) {
                dp[r][n - 1][j] = dp[(k + r - grid[n - 1][j] % k) % k][n - 1][j + 1];
            }
        }


        for (int i = n-2; i >=0 ; i--) {
            for (int j =m-2 ; j>=0 ; j--) {
                for (int r = 0; r < k; r++) {
                    int need = (k + r - (grid[i][j] % k)) % k;
                    dp[r][i][j] = dp[need][i + 1][j];
                    dp[r][i][j] = (dp[r][i][j] + dp[need][i][j + 1]) % mod;
                }
            }
        }
        return dp[0][0][0];
    }

    public int mod = 1000000007;

    /**
     *
     * @param grid
     * @param n
     * @param m
     * @param k
     * @param i
     * @param j
     * @param r  剩余达到目标的余数
     * @return
     */
    private int f2(int[][] grid, int n, int m, int k, int i, int j, int r) {
        if (i == n - 1 && j == m - 1) {
            return grid[i][j] % k == r ? 1 : 0;
        }
        // 后续需要凑出来的余数need  todo (观察) 同余原理  没有f1Myself好理解 但是dp的时候count会比较大
        // 也可以条件转移
        // if(grid[i][j] % k)<=r  need= r-
        // if(grid[i][j] % k)>r
        int need = (k + r - (grid[i][j] % k)) % k;
        int ans = 0;
        if (i + 1 < n) {
            ans = f2(grid, n, m, k, i + 1, j, need);
        }
        if (j + 1 < m) {
            ans = (ans + f2(grid, n, m, k, i, j + 1, need)) % mod;
        }
        return ans;
    }

    /**
     * 虽然f1Myself 实习简单并且原理简单，但是count的数组长度是大于f2 的余数长度，所以采用f2动态规划
     * @param grid
     * @param k
     * @return
     */
    private int f3(int[][] grid, int k) {
        int n =grid.length;
        int m =grid[0].length;
        int[][][] dp =new int[k][n][m];
        return 0;
    }

    private int f1Myself(int[][] grid, int k,int i,int j,int count) {
        //base case
        int n =grid.length;
        int m =grid[0].length;
        if(n-1==i&&m-1==j){
            return count%k==0?1:0;
        }
        int ans = 0;
        if(i+1<n){//走下
            ans+= f1Myself(grid,k,i+1,j,count+grid[i+1][j]);
        }
        if(j+1<m){
            ans+=f1Myself(grid,k,i,j+1,count+grid[i][j+1]);
        }
        return ans;
    }
}
